package Stack_Queue;

import java.util.Stack;

/*
* 逆波兰表达式主要有以下两个优点：
去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中
*
* 示例 1：
输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
*
示例 2：
输入：tokens = ["4","13","5","/","+"]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
* */
public class lc150 {
    public static void main(String[] args) {
        String[] tokens=new String[]{"4","13","5","/","+"};
        System.out.println(evalRPN(tokens));

    }
    public static int evalRPN(String[] tokens) {
        Stack<String> stack=new Stack<>();
        int a=0;
        int b=0;
        for (String str:tokens) {
            if(str.equals("+")){
                a=Stringtonumber(stack.pop());
                b=Stringtonumber(stack.pop());
                int c=b+a;
                String str_c=c+"";
                stack.push(str_c);
            }else if(str.equals("/")){
                a=Stringtonumber(stack.pop());
                b=Stringtonumber(stack.pop());
                int c=b/a;
                String str_c=c+"";
                stack.push(str_c);
            }else if(str.equals("*")){
                a=Stringtonumber(stack.pop());
                b=Stringtonumber(stack.pop());
                int c=b*a;
                String str_c=c+"";
                stack.push(str_c);
            }else if(str.equals("-")){
                a=Stringtonumber(stack.pop());
                b=Stringtonumber(stack.pop());
                int c=b-a;
                String str_c=c+"";
                stack.push(str_c);
            }else {
                stack.push(str);
            }
        }
        String re=stack.pop();
        return Stringtonumber(re);
    }
    public static int Stringtonumber(String str){
        char[] chars = str.toCharArray();
        int result=0;
        if(chars[0]!='-') {
            for (int i = 0; i <str.length() ; i++) {
                result=result*10+(chars[i]-'0');
            }
        }else{
            for (int i = 1; i <str.length() ; i++) {
                result=result*10+(chars[i]-'0');
            }
            result=result*(-1);
        }
        return result;
    }
}
